﻿// 0911train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
小华按照地图去寻宝，地图上被划分成 m 行和 n 列的方格，横纵坐标范围分别是 [0, n-1] 和 [0, m-1]。
在横坐标和纵坐标的数位之和不大于 k 的方格中存在黄金（每个方格中仅存在一克黄金），
但横坐标和纵坐标数位之和大于 k 的方格存在危险不可进入。
小华从入口 (0,0) 进入，任何时候只能向左，右，上，下四个方向移动一格。 请问小华最多能获得多少克黄金？

输入描述
坐标取值范围如下： 0 ≤ m ≤ 50，0 ≤ n ≤ 50
k 的取值范围如下： 0 ≤ k ≤ 100
输入中包含 3 个字数，分别是 m, n, k

输出描述
输出小华最多能获得多少克黄金

输入
40 40 18
输出
1484
 */
class Solution01
{
public:
    int getSum(int num)
    {
        int result = 0;
        while (num>0)
        {
            result += num%10;
            num = num / 10;
        }
        return result;
		//getSum
    }

    void solve01(int row_size, int col_size, int limit)
    {
        vector<vector<int>>grid(row_size, vector<int>(col_size));

        vector<vector<bool>>checked(row_size, vector<bool>(col_size));

        deque<vector<int>>bfs_queue;
        bfs_queue.push_back({ 0,0 });
        checked[0][0] = true;
        result += 1;

        while (!bfs_queue.empty())
        {
            vector<int>top_node = bfs_queue.front();
            bfs_queue.pop_front();

            for (auto& dir_v : DirectionGrid)
            {
                int curr_r = top_node[0] + dir_v[0];
                int curr_c = top_node[1] + dir_v[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                //未访问 不越界 符合要求
                if (is_curr_r && is_curr_c)
                {
                    //横坐标和纵坐标的数位之和不大于 k
                    bool is_visited = checked[curr_r][curr_c];
                    bool is_available = getSum(curr_r) + getSum(curr_c) <= limit;

                    if (!is_visited && is_available)
                    {
                        //更新结果，入队列
                        //标记已访问
                        checked[curr_r][curr_c] = true;
                        result += 1;
                        bfs_queue.push_back({ curr_r,curr_c });
                    }

                }

                //for (auto&dir_v
            }


            //while (!bfs_queue.empty())
        }
        cout << result;
    }

    Solution01(int row_size, int col_size, int limit)
    {
        solve01(row_size, col_size, limit);

	    //Solution01
    }
private:
    int result = 0;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};

/*
 题目描述
在一个机房中，服务器的位置标识在 n*m 的整数矩阵网格中，
1表示单元格上有服务器，0 表示没有。
如果两台服务器位于同一行或者同一列中紧邻的位置，则认为它们之间可以组成一个局域网
请你统计机房中最大的局域网包含的服务器个数

输入描述
第一行输入两个正整数，n和m，0 < n,m <= 100
之后为n*m的二维数组，代表服务器信息

输出描述
最大局域网包含的服务器个数

输入
2 2
1 0
1 1
输出
3
[0][0]、[1][0]、[1][1]三台服务器相互连接，可以组成局域网
 */

class Solution02
{
public:
    void bfsUpdate(
        vector<vector<int>>& grid, 
        vector<vector<bool>>&checked,
        deque<vector<int>>&bfs_queue)
    {
        while (!bfs_queue.empty())
        {
            vector<int>top_node = bfs_queue.front();
            bfs_queue.pop_front();

            for (auto&dir_vec: DirectionGrid)
            {
                int curr_r = top_node[0] + dir_vec[0];
                int curr_c = top_node[1] + dir_vec[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                if (is_curr_r&&is_curr_c)
                {
                    bool is_visited = checked[curr_r][curr_c];
                    bool is_available = grid[curr_r][curr_c] == 1;

                    if (!is_visited&&is_available)
                    {
                        //标记已访问
                        checked[curr_r][curr_c] = true;
                        //结果+1
                        curr_count += 1;
                        bfs_queue.push_back({ curr_r,curr_c });
                    }

                }

            }

            //bfs_queue
        }
        

        //bfsUpdate
    }

    Solution02(vector<vector<int>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        vector<vector<bool>>checked(row_size, vector<bool>(col_size, false));

        deque<vector<int>>bfs_queue;

        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                if (!checked[r][c] && grid[r][c]==1)
                {
                    bfs_queue.push_back({ r,c });
                    //标记已访问
                    checked[r][c] = true;
                    curr_count = 1;
                    bfsUpdate(grid, checked, bfs_queue);
                    result = max(result, curr_count);
                }

                //col_size
	        }
            //row_size
        }
        cout << result;
	    //Solution02
    }
private:
    int curr_count = 0, result = 0;
    int row_size = 0, col_size = 0;
    vector<vector<int>>DirectionGrid = {{-1,0},{1,0},{0,-1},{0,1}};
};


/*
 XX市机场停放了多架飞机，每架飞机都有自己的航班号CA3385，CZ6678，SC6508等，航班号的前2个大写字母)
 （或数字）代表航空公司的缩写，后面4个数字代表航班信息
 但是XX市机场只有一条起飞用跑道，调度人员需要安排目前停留在机场的航班有序起飞
为保障航班的有序起飞，调度员首先按照航空公司的缩写(航班号前2个字母或数字)对所有航班进行排序，
同一航空公司的航班再按照航班号的后4个数字进行排序最终获得安排好的航班的起飞顺序
请编写一段代码，根据输入的航班号信息，帮助调度员输出航班的起飞顺序

输入描述
第一行输入航班信息，多个航班号之间用逗号","分隔，输入的航班号不超过100个

输出描述
一行航班信息表示安排好的航班起飞顺序

补充说明
航班号为6位长度，后4位为纯数字，不考虑存在后4位重复的场景
航空公司缩写排序按照从特殊符号$ & *，0~9，A~Z排序

输入
CA3385,CZ6678,SC6508,DU7523,HK4456,MK0987
输出
CA3385,CZ6678,DU7523,HK4456,MK0987,SC6508
 */
class Solution03
{
public:
    static int compareChar(char char_1, char char_2)
    {
        //1<2 1 2 相等0
        //$ & *，0~9，A~Z
        if (char_1 == char_2) return 0;
        vector<char>special = {'$','&','*'};
        bool is_special_1 = false;
        bool is_special_2 = false;

        for (auto&s_char:special)
        {
            if (char_1 == s_char) is_special_1 = true;
            if (char_2 == s_char) is_special_2 = true;
        }

        if (is_special_1 && !is_special_2) return 1;
        if (!is_special_1 && is_special_2) return 2;
        if (is_special_1 && is_special_2) return 0;

        //数字比较
        bool is_num_1 = isdigit(char_1);
        bool is_num_2 = isdigit(char_2);
        if (is_num_1 && !is_num_2) return 1;
        if (!is_num_1 && is_num_2) return 2;
        if (is_num_1 && is_num_2)
        {
            int num_1 = char_1 - '0';
            int num_2 = char_2 - '0';
            if (num_1 < num_2) return 1;
            return 2;
        }

        //两个都不是数字
        //字符比较
        if (char_1 < char_2) return 1;
        return 2;

    }

    static bool compare(const string&str_1, const string&str_2)
    {
        int char_res0 = compareChar(str_1[0], str_2[0]);
        if (char_res0 == 0)
        {
            //相等再比一轮
            int char_res1 = compareChar(str_1[1], str_2[1]);
            if (char_res1 == 1) return true; //str_1<str_2
            return false;
        }
        else if (char_res0 == 1)
        {
            return true;//str_1<str_2
        }
        return false;
        //compare
    }

    Solution03(vector<string>&str_vec)
    {
        //1航班号前2个字母或数字排序
        //2按照航班号的后4个数字进行排序

        //先按航班号，推进map里
        //map_item.first全部推进一个数组，排序
        //按照从特殊符号$ & *，0~9，A~Z排序

        unordered_map<string, vector<pair<string,int>>>kind_map;
        for (auto&str:str_vec)
        {
            string kind = str.substr(0, 2);
            string num_str = str.substr(2);
            kind_map[kind].push_back(make_pair(num_str, stoi(num_str)));
        }

        vector<string>kind_sort_v;
        for (auto&map_item:kind_map)
        {
            kind_sort_v.push_back(map_item.first);
        }

        sort(kind_sort_v.begin(), kind_sort_v.end(), compare);

        vector<string>result;

        for (auto&kind_item:kind_sort_v)
        {
            vector<pair<string, int>>kind_vec = kind_map[kind_item];
            sort(kind_vec.begin(), kind_vec.end(), [](pair<string, int>& p_1, pair<string, int>& p_2)
                {
                    return p_1.second < p_2.second;
                });

            for (auto&p_item:kind_vec)
            {
                result.push_back(kind_item + p_item.first);
            }
        }

        for (int i=0; i<result.size(); i++)
        {
            cout << result[i];
            if (i!=result.size()-1)
            {
                cout << ',';
            }
        }

        //Solution03
    }
};


int main()
{
	{
        string input = "$A3385,C56678,SC6508,DU7523,HK4456,MK0987";
        //string input;
        //getline(cin, input);
        vector<string>str_vec;
        stringstream oh_sstream(input);
        string token;
        while (getline(oh_sstream,token,','))
        {
            str_vec.push_back(token);
        }
        Solution03 solu(str_vec);
        return 0;
	}
	{
/*
2 2
1 0
1 1
*/
        int row_size, col_size;
        cin >> row_size >> col_size;
        vector<vector<int>>grid(row_size, vector<int>(col_size));
        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                cin >> grid[r][c];
	        }
        }
        Solution02 solu(grid);

        return 0;
	}
    int row_size, col_size, limit;
    cin >> row_size >> col_size >> limit;

    Solution01 solu(row_size, col_size, limit);

    //cout << solu.getSum(44);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
